package algocasts;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class P137_FindAllNumbersDisappearedInAnArray {
    // Time: O(n)  Space: O(n)
    public List<Integer> findDisappearedNumbers(int[] nums) {
        if (nums == null || nums.length == 0) return Collections.emptyList();
        List<Integer> result = new ArrayList<>();
        boolean[] existed = new boolean[nums.length];
        for (int num : nums) existed[num - 1] = true;
        for (int i = 0; i < existed.length; i++)
            if (!existed[i])
                result.add(i + 1);
        return result;
    }

    // Time: O(n)  Space: O(1)
    public List<Integer> findDisappearedNumbers_O1(int[] nums) {
        if (nums == null || nums.length == 0) return Collections.emptyList();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] > 0) nums[idx] = -nums[idx];
        }
        for (int i = 0; i < nums.length; i++)
            if (nums[i] > 0)
                result.add(i + 1);
        return result;
    }

}
